'''
candidate set = [10, 1, 2, 7, 6, 1, 5]
target = 8

sort first: [1,1,2,5,6,7,10]

solution set =
[
    [1,7],
    [1,2,5],
    [2,6],
    [1,1,6]
]
'''
class Solution(object):
    def combinationSum2(self, candidates, target):
        res = []
        candidates.sort()
        self.dfs(candidates, target, 0, [], res)
        return res

    def dfs(self, candidates, target, ind, path, res):
        if target == 0:
            res.append(path)
            return
        for i in range(ind, len(candidates)):
            if candidates[i] > target:
                break
            if i-1 >= ind and candidates[i] == candidates[i-1]:
                continue
            self.dfs(candidates,target - candidates[i],i+1, path + [candidates[i]], res)
        
s = Solution()
can = [1,1,2,5,6,7,10]
print s.combinationSum2(can,8)
